package interview.combineintervals;

import java.util.ArrayList;
import java.util.Collections;
import java.util.Iterator;
import java.util.List;

public class CombineIntervals {
	
	public List<Interval> run(List<Interval> set1, List<Interval> set2) {
		Collections.sort(set1);
		Collections.sort(set2);

		List<Interval> nset1 = mergeIntervals(set1);
		List<Interval> nset2 = mergeIntervals(set2);

		return combineIntervals(nset1, nset2);
	}

	private static List<Interval> combineIntervals(List<Interval> intervalSet1,
			List<Interval> intervalSet2) {
		List<Interval> result = new ArrayList<Interval>();
		Iterator<Interval> li1 = intervalSet1.iterator();
		Iterator<Interval> li2 = intervalSet2.iterator();

		Interval cur1 = null;
		Interval cur2 = null;
		while (li1.hasNext() && li2.hasNext()) {
			if (cur1 == null) {
				cur1 = li1.next();
			}
			if (cur2 == null) {
				cur2 = li2.next();
			}
			
			int cmp = cur1.compareTo(cur2);
			if (cmp == 0) {
				if (cur1.getHigher() < cur2.getHigher()) {
					cur2.setLower(Math.min(cur1.getLower(), cur2.getLower()));
					cur1 = null;
				} else if ( cur1.getHigher() > cur2.getHigher()) {
					cur1.setLower(Math.min(cur1.getLower(), cur2.getLower()));
					cur2 = null;
				} else {
					result.add(cur1.combine(cur2));
					cur1 = null;
					cur2 = null;
				}
			} else if (cmp == -1) {
				result.add(cur1);
				cur1 = null;
			} else if (cmp == 1) {
				result.add(cur2);
				cur2 = null;
			}
		}
		
		if(cur1 != null)
			result.add(cur1);
		
		if(cur2 != null)
			result.add(cur2);
		
		while (li1.hasNext()) {
			result.add(li1.next());
		}
		
		while (li2.hasNext()) {
			result.add(li2.next());
		}

		return result;
	}

	private static List<Interval> mergeIntervals(List<Interval> intervalSet) {
		List<Interval> result = new ArrayList<Interval>();
		Interval current = null;
		for (Interval interval : intervalSet) {
			if (current == null) {
				current = interval;
			} else {
				int cmp = current.compareTo(interval);
				if (cmp == 0) {
					current = current.combine(interval);
				} else {
					result.add(current);
					current = interval;
				}
			}
		}
		
		result.add(current);
		
		return result;
	}
}
